package com.zlk.algorithm.algorithm.dynamicPlan.twoDimension.more;

// 有效涂色问题
// 给定n、m两个参数
// 一共有n个格子，每个格子可以涂上一种颜色，颜色在m种里选
// 当涂满n个格子，并且m种颜色都使用了，叫一种有效方法
// 求一共有多少种有效的涂色方法
// 1 <= n, m <= 5000
// 结果比较大请 % 1000000007 之后返回
// 对数器验证
public class Code04_FillCellsUseAllColorsWays {

    /**
     * 暴力可能性分析
     * dp含义      前i个格子 已经涂了j种颜色
     * dp[5][3]   意思就是前5个格子要凑齐三种颜色
     * dp[i][j]    1、dp[i-1]*j  (前面格子已经满了 最后一个格子就是随便取了)
     *             2、dp[i-1][j-1]*(m-(j-1))
     *             (核心理解要必须要凑满dp含义就是凑齐 所以当前位置必须至少一个，不能少2个，只能少一个
     *             前面格子没满少一种，最后得格子得补上，一共颜色m种剩下就是m-(j-1))
     *
     *
     * @param n
     * @param m
     * @return
     */
    // 正式方法
    // 时间复杂度O(n * m)
    // 已经展示太多次从递归到动态规划了
    // 直接写动态规划吧
    // 也不做空间压缩了，因为千篇一律
    // 有兴趣的同学自己试试
    public static int MAXN = 5001;

    public static int[][] dp = new int[MAXN][MAXN];

    public static int mod = 1000000007;


    public static int ways2(int n, int m) {
        // dp[i][j]:
        // 一共有m种颜色
        // 前i个格子涂满j种颜色的方法数
        for (int i = 1; i <= n; i++) {
            dp[i][1] = m;
        }
        for (int i = 2; i <= n; i++) {
            for (int j = 2; j <= m; j++) {
                dp[i][j] = (int) (((long) dp[i - 1][j] * j) % mod);
                dp[i][j] = (int) ((((long) dp[i - 1][j - 1] * (m - j + 1)) + dp[i][j]) % mod);
            }
        }
        return dp[n][m];
    }



}
